參見課程網站 http://ccf.ee.ntu.edu.tw/~yen/courses/TOC-2024.html

This course provides a rigorous, graduate level introduction to Automata Theory, Formal Languages, and Complexity. Topics to be covered will include:

(1). Finite automata, Regular languages, Regular grammars:
Deterministic vs. nondeterministic, one-way vs. two-way finite automata, minimization,
pumping lemma for regular sets, closure properties.

(2). Pushdown automata, Context-free languages, Context-free grammars:
Deterministic vs. nondeterministic, one-way vs. two-way PDAs, reversal bounded PDAs,
linear grammars, counter machines, pumping lemma for CFLs, Chomsky normal form,
Greibach normal form, closure properties.

(3). Linear bounded automata, Context-sensitive languages, Context-sensitive grammars.

(4). Turing machines, Recursively enumerable sets, Type 0 grammars:
Variants of Turing machines, halting problem, undecidability, Post correspondence
problem, valid and invalid computations of TMs.

(5). Basic recursive function theory

(6). Basic complexity theory:
Various resource bounded complexity classes, including NLOGSPACE, P, NP,
PSPACE, EXPTIME, and many more. reducibility, completeness.

(7). Advanced topics in complexity theory:
Approximation algorithms, probabilistic complexity, parallel complexity, Alternation,
interactive proof systems, oracle computations.